package com.qz.sort;

import java.util.*;

/**
 * @Description 基数排序
 * @Author Flag
 * @Date: 2021/8/9 8:38
 * @Version: 1.0
 **/
public class RadixSortDome {
    public static void main(String[] args) {

        int[] array = {53,3,542,748,14,214};
        int[] ints = radixSort3(array);


        System.out.println(Arrays.toString(ints));


    }

    /**
     * 基数排序
     * @param array
     * @return
     */
    public static int[] radixSort(int[] array){
        //初始化一个数组
        List<Deque<Integer>> list = new ArrayList<>();
        for (int i = 0; i < 10; i++) {
            list.add(new ArrayDeque<>());
        }

        //求出数组的最大的位数
        int maxPlace = 0;
        int number;
        int temPlace ;
        for (int i = 0; i < array.length; i++) {

            number = array[i];
            temPlace = 0;
            while (number !=0){
                number /=10;
                temPlace++;
            }
            if(temPlace>maxPlace){
                maxPlace = temPlace;
            }
        }

        int result;
        for (int j = 1; j < maxPlace ; j++) {
            for (int i = 0; i < array.length; i++) {

                result = array[i]% (int)Math.pow(10,j) / (int)Math.pow(10,j-1);
                Deque<Integer> integers = list.get(result);
                integers.addLast(array[i]);

            }

            //将数据放回到数中
            ArrayDeque arrayDeque = new ArrayDeque();

            int index=0;
            Integer temp = null;
            for (Deque<Integer> integers : list) {
                for (Integer integer: integers) {
                    if((temp =integers.poll())!=null){
                        array[index] = temp;
                        index++;
                    }
                }
            }
        }
        return array;
    }


    /**
     * 基数排序， 从小到大
     * 核心思想  创建一个二维数组，先按照个位放入对应的桶，然后从头再将数据拿出来，在按照十位放入对应的桶里面
     * @param array
     * @return
     */
    public static int[] radixSort2(int[] array){
        //求出数组中最高的位数
        int max = 0;
        for (int i = 0; i < array.length; i++) {
            if(array[i]>max){
                max = array[i];
            }
        }

        //求出最大的位数
        int maxPlace = 0;
        while (max>0){
            max /=10;
            maxPlace ++;
        }



        //定义一个二维数组，用来充当桶
        int[][] tempArray = new int[10][array.length];
        //定义一个数组，用来存放桶的指针
        int[] tempArrayIndex = new int[10];
        //定义一个中间变了
        int temp = 0;
        //遍历每一位数
        for (int i = 0; i < maxPlace; i++) {
            //初始化数组
            for (int j = 0; j < tempArrayIndex.length; j++) {
                tempArrayIndex[j]  = 0;
            }
            //遍历每一个元素
            for (int j = 0; j < array.length; j++) {
                //求出对应的的位注，第一个位就是个位，第二位就是十位
                temp = array[j] / (int)Math.pow(10,i) % 10;
                tempArray[temp][tempArrayIndex[temp]] = array[j];
                tempArrayIndex[temp]++;
            }

            //将数组的元素放入到集合中


            int tempIndex = 0;
            for (int k = 0; k < tempArrayIndex.length; k++) {
                for (int j = 0; j < tempArrayIndex[k]; j++) {
                    int i1 = tempArray[k][j];
                    array[tempIndex] = i1;
                    tempIndex++;

                }
            }
        }

        return array;
    }


    /**
     * 基数排序
     * 从小到大
     * 1.求出最大的数值
     * 2.求出最大熟知的位数
     * 3.然后创建一个二维数组
     * 4.每一位都取余，然后放入到对应的桶中
     * 5.在把桶中的数据放回到数组中
     *
     * @param array
     * @return
     */
    public static int[] radixSort3(int[] array){


        //1.求出最大的数值
        int maxValue = array[0];
        for (int i = 1; i < array.length; i++) {
            if (maxValue < array[i]) {
                maxValue = array[i];
            }
        }
        //2.求出最大熟知的位数
        int maxPlace = 0;
        while (maxValue >= 1){
            maxPlace ++;
            maxValue /= 10;
        }

        //3.然后创建一个二维数组
        int[][] bucketArray = new int[10][array.length];
        int[] bucketIndex = new int[10];


        int temp = 0;
        //4.每一位都取余，然后放入到对应的桶中
        for (int i = 1,n=1; i < maxPlace+1; i++,n*=10) {
            //初始化数组
            for (int j = 0; j < bucketIndex.length ;j++) {
                bucketIndex[j] = 0;
            }
            //543  %100 43 /10
            for (int j = 0; j < array.length; j++) {
//                temp = array[j] % (n) / 10;
                temp = array[j] / n% 10;
                bucketArray[temp][bucketIndex[temp]] = array[j];
                bucketIndex[temp] ++ ;
            }


            //5.在把桶中的数据放回到数组中
            int beginIndex = 0;
            for (int j = 0; j < bucketIndex.length; j++) {
                for (int k = 0; k < bucketIndex[j]; k++) {
                    array[beginIndex] =  bucketArray[j][k];
                    beginIndex++;
                }

            }


            System.out.println(Arrays.toString(array));

        }
        return array;

    }
}
